/**
 * 简单排序
 * @returns
 */
export function simpleSort(): Array<number> {
  var a = [7, 5, 9, 4, 8, 2, 0, 12, 10, 6];
  for (let i = 0; i < a.length; i++) {
    for (let j = i + 1; j < a.length; j++) {
      if (a[j + 1] < a[i]) {
        let temp = a[i];
        a[i] = a[j + 1];
        a[j + 1] = temp;
      }
    }
  }
  return a;
}

/**
 * 冒泡排序
 * @returns
 */
export function bubbleSort(): Array<number> {
  var a = [7, 5, 9, 4, 8, 2, 0, 12, 10, 6];
  for (let i = 0; i < a.length; i++) {
    let isSwap = false;
    for (let j = 0; j < a.length; j++) {
      if (a[j + 1] < a[j]) {
        let temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
        isSwap = true;
      }
    }
    if (!isSwap) {
      break;
    }
  }
  return a;
}

/**
 * 快速排序
 * @param a
 * @param left
 * @param right
 */
function quckSortDeep(a, left, right) {
  if (left < right) {
    let temp = a[left];
    let i = left,
      j = right;
    while (i < j) {
      // 从右边找到第一个小于基准的数
      while (i < j && a[j] > temp) {
        j--;
      }
      if (i < j) {
        a[i++] = a[j];
      }
      // 从左边找到第一个大于基准的数
      while (i < j && a[i] < temp) {
        i++;
      }
      if (i < j) {
        a[j--] = a[i];
      }
    }
    a[i] = temp;
    quckSortDeep(a, left, i - 1);
    quckSortDeep(a, i + 1, right);
  }
}

/**
 * 快速排序
 * @returns
 */
export function quickSort(): Array<number> {
  var a = [7, 5, 9, 4, 8, 2, 0, 12, 10, 6];
  quckSortDeep(a, 0, a.length - 1);
  return a;
}

/**
 * 插入排序
 */
export function insertSort(): Array<number> {
  var a = [7, 5, 9, 4, 8, 2, 0, 12, 10, 6];
  // i从1开始,1前面的索引都是排序好的
  for (let i = 1; i < a.length; i++) {
    let j = i - 1;
    let next = a[i];
    while (j >= 0) {
      if (next < a[j]) {
        let temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
        j--;
      } else {
        break;
      }
    }
  }
  return a;
}

/**
 * 获取当前值所在第几个桶
 * @param min 最小值
 * @param max 最大值
 * @param count 桶的个数
 */
function calcIndex(min: number, max: number, count: number): Function {
  const remain = (max - min) % count;
  const step = (max + remain - min) / count;
  return function(num: number) {
    // 保证最小数左闭
    if (num == min) {
      return 0;
    }
    // 保证右闭
    if ((num - min) % step == 0) {
      return (num - min) / step - 1;
    }
    // 其他数直接取底数
    return Math.floor((num - min) / step);
  };
}

/**
 * 桶排序
 */
export function bucketSort(): Array<number> {
  // [0, 4], (4, 8], (8, 12]
  const a = [7, 5, 9, 4, 8, 2, 0, 12, 10, 6];
  const result = [];
  let max = Number.MIN_VALUE;
  let min = Number.MAX_VALUE;
  const length = a.length;
  for (let i = 0; i < length; i++) {
    if (a[i] < min) {
      min = a[i];
    }
    if (a[i] > max) {
      max = a[i];
    }
  }
  const bucket = [[], [], []];
  const getIndex = calcIndex(min, max, bucket.length);
  for (let i = 0; i < length; i++) {
    const index = getIndex(a[i]);
    bucket[index].push(a[i]);
  }
  for (let i = 0; i < bucket.length; i++) {
    if (bucket[i].length > 1) {
      quckSortDeep(bucket[i], 0, bucket[i].length - 1);
    }
    result.push(...bucket[i]);
  }
  return result;
}

class ListNode {
  public val;

  public next;

  constructor(val, next) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

export const addTwoNumbers = function(l1, l2) {
  let last = 0;
  let head;
  let current;
  while (l1 != null && l2 != null) {
    const result = l1.val + l2.val + last;
    last = Math.floor(result / 10);
    let cur = new ListNode(result % 10, null);
    if (current) {
      current.next = cur;
    }
    current = cur;
    if (head == null) {
      head = current;
    }
    // 下一个节点
    l1 = l1.next;
    l2 = l2.next;
  }
  let remainNode = l1 == null ? l2 : l1;
  while (remainNode != null) {
    const result = remainNode.val + last;
    last = Math.floor(result / 10);
    let cur = new ListNode(result % 10, null);
    if (current) {
      current.next = cur;
    }
    current = cur;
    if (head == null) {
      head = current;
    }
    remainNode = remainNode.next;
  }
  return head;
};

export function test() {
  function generate(arr) {
    let first;
    let currentFirst;
    arr.forEach((i) => {
      let cur = new ListNode(i, null);
      if (currentFirst) {
        currentFirst.next = cur;
      }
      currentFirst = cur;
      if (first == null) {
        first = cur;
      }
    });
    return first;
  }
  addTwoNumbers(generate([9, 9, 9, 9, 9, 9, 9]), generate([9, 9, 9, 9]));
}

class Tree {
  private value: number;

  private left: number;

  private right: number;

  public constructor(value: number) {
    this.value = value;
  }
}

export function buildTree(values: number[], node: Tree, i: number) {
  let head = null;
}

var a = [
  { id: 1, department: "ni", parentId: null },
  { id: 2, department: "hao", parentId: 1 },
  { id: 3, department: "ceshi", parentId: 2 },
];

const record = {};

for (let i = 0; i < a.length; i++) {}
